//给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。 
//
// 数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复） 
//
// 返回数组的 第 k 大和 。 
//
// 子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。 
//
// 注意：空子序列的和视作 0 。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [2,4,-2], k = 5
//输出：2
//解释：所有可能获得的子序列和列出如下，按递减顺序排列：
//- 6、4、4、2、2、0、0、-2
//数组的第 5 大和是 2 。
// 
//
// 示例 2： 
//
// 输入：nums = [1,-2,3,4,-10,12], k = 16
//输出：10
//解释：数组的第 16 大和是 10 。
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// 1 <= k <= min(2000, 2ⁿ) 
// 
//
// Related Topics 数组 排序 堆（优先队列） 👍 86 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2024-03-09 01:05:09
 * @description 2386.找出数组的第 K 大和
 */
public class FindTheKSumOfAnArray{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new FindTheKSumOfAnArray().new Solution();
		 solution.kSum(new int[]{-1,1,0,2,3},2);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*
		 * 二分+暴力搜索
		 * 假设已经得到非负数和为sum
		 * 此时加上一个负数，或者减去一个正数
		 * 都相当于减去这个数的绝对值
		 * 因此将问题转化为，将每个数取绝对值后
		 * 数组第k个小的序列化是多少
		 * 假设当前答案为sumL,问题转化为是否有至少k个子序列，
		 * 元素和不超过sumL
		 * 从小到大对于每个数组元素选或者不选
		 * 递归中，如果已经选了k个或者和大于sumL时结束
		 * 前者说明已经选了K个，后面说明子序列和太大
		 * 下界为0，下界为所有元素绝对值的和
		 * 用sum减去二分得到的值即为答案
		 * 因为非负数的和sum即为最大，再减去一个最小值则为次大
		 * 减去第k小，则为第k大的
		 * */
    public long kSum(int[] nums, int k) {
		//非负数和以及二分上边界
		long sum=0,r=0;
		for (int i = 0; i < nums.length; i++) {
			if(nums[i]>=0){
				sum+=nums[i];
			}else {
				nums[i]=-nums[i];
			}
			r+=nums[i];
		}
		Arrays.sort(nums);

		long l=-1;
		while (l+1<r){
			long m=(l+r)/2;
			cnt=k-1;//空子序列也算，直接减去
			dfs(0,m,nums);
			if(cnt==0){
				r=m;
			}else {
				l=m;
			}
		}
		return sum-r;
    }
	private  int cnt;
	private void dfs(int i,long s,int [] nums){
         if(cnt==0||i==nums.length||s<nums[i]){
			 return;
		 }
		 cnt--;
		 dfs(i+1,s-nums[i],nums);//选
		 dfs(i+1,s,nums);//不选
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
